package leetcode;

import java.util.ArrayList;
import java.util.List;

public class PalidromePartition {

	public static void main(String[] args) {
		PalidromePartition pa = new PalidromePartition();
		List<List<String>> res = pa.partition("aabcbd");
		for (List<String> list : res) {
			System.out.println(list);
		}
	}

	public List<List<String>> partition(String s) {
		List<List<String>> res = new ArrayList<List<String>>();
		if (s == null || s.length() <= 0) {
			return res;
		}
		List<String> list = new ArrayList<String>();
		backtrack(res, list, s, 0, s.length());
		return res;
	}

	public void backtrack(List<List<String>> res, List<String> list,
			String string, int start, int length) {
		if (start == length) {
			res.add(new ArrayList<String>(list));
		}
		// if(list.size() == string.length){
		// if(isPalidrome(Arrays.toArray(list))){
		// temp.add(String.valueOf(Arrays.toArray(list)));
		// res.add(temp);
		// }
		// return;
		// }
		List<String> temp = new ArrayList<>();
		for (int i = start; i < length; i++) {
			if (isPalidrome(string.substring(start, i + 1).toCharArray())) {
				temp = new ArrayList<>(list);
				list.add(string.substring(start, i + 1));
				backtrack(res, list, string, i + 1, length);
				list = temp;
				// list.indexOf(string.substring(start, i + 1));
				// list.clear();
				// list.remove(list.size() - 1);
			}
		}
	}

	// 判断是否是回文串
	public boolean isPalidrome(char[] s) {
		for (int i = 0; i < s.length / 2; i++) {
			if (s[i] != s[s.length - 1 - i]) {
				return false;
			}
		}
		return true;
	}

	// 将字符串变成回文串最少切割数
	public int minCut(String s) {
		if (s == null || s.length() <= 0) {
			return 0;
		}
		char[] chas = s.toCharArray();
		int length = chas.length;
		// dp[i] 表示子串str[i ... length - 1]至少要切割几次
		int[] dp = new int[length + 1];
		dp[length] = -1;
		// 判断str[i...j]是否是回文
		boolean[][] isPalidrome = new boolean[length][length];
		for (int i = length - 1; i >= 0; i--) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = i; j < length; j++) {
				// isPalidrome[i][j]如果是回文只有三种情况1、 i == j
				// 2、j = i + 1, 且两个字符相等
				// 3、chas[i] == chas[j]isPalidrome[i + 1][j - 1]为true
				if (chas[i] == chas[j]
						&& (j - i < 2 || isPalidrome[i + 1][j - 1])) {
					isPalidrome[i][j] = true;
					dp[i] = Math.min(dp[j + 1] + 1, dp[i]); // 取所有的j中的最小值 + 1
				}
			}
		}
		return dp[0];
	}
	
	public int minCut2(String s) {
		if (s == null || s.length() <= 0) {
			return 0;
		}
		char[] chas = s.toCharArray();
		int length = chas.length;
		// dp[i] 表示子串str[i ... length - 1]至少要切割几次
		int[] dp = new int[length];
		dp[length - 1] = 0;
		// 判断str[i...j]是否是回文
		boolean[][] isPalidrome = new boolean[length][length];
		for (int i = length - 2; i >= 0; i--) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = i; j < length; j++) {
				// isPalidrome[i][j]如果是回文只有三种情况1、 i == j
				// 2、j = i + 1, 且两个字符相等
				// 3、chas[i] == chas[j]isPalidrome[i + 1][j - 1]为true
				if (chas[i] == chas[j]
						&& (j - i < 2 || isPalidrome[i + 1][j - 1])) {
					isPalidrome[i][j] = true;
					if(j == length - 1){
					    dp[i] = Math.min(0, dp[i]);	//此时根本就不用切割
					}else{
					    dp[i] = Math.min(dp[j + 1] + 1, dp[i]); // 取所有的j中的最小值 + 1
					}
				}
			}
		}
		return dp[0];
	}
}
